package com.lx.algorithm.Tree;

import static com.lx.algorithm.Tree.TreeUtils.generateRandomBST;

/**
 * Description: 判断一个二叉树是不是一个满二叉树
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-10-19 15:11:47
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-10-19     张李鑫                     1.0         1.0 Version
 */
public class IsFull {

    /**
     * 满二叉树代表每个树都有左右两个节点
     */

    public static class Info {
        public boolean isFull;
        public int height;

        public Info(int height, boolean isFull) {
            this.isFull = isFull;
            this.height=height;
        }
    }


    public static boolean isFull(Node node) {
        return process(node).isFull;
    }


    /**
     * <p>
     * 写的没有老师给的代码好
     * 老师给的代码只记录高度跟个数
     * 个数==左右树的个数之和
     * 宽度等于左右树的最大宽度
     * </p>
     *
     * @param node
     * @return com.lx.algorithm.Tree.IsFull.Info
     * @Author zlx
     * @date 2021/10/19
     */
    public static Info process(Node node) {
        if (node == null) {
            return new Info(0,true);
        }
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);
        boolean isFull = true;
        //如果左右节点都有的话。 高度一样算满
        if (node.left != null && node.right != null) {
            isFull = leftInfo.height == rightInfo.height;
            //如果都没有默认是最后一个节点
        } else if (node.left == null && node.right == null) {
            isFull = true;
        } else {
            //否则全部视为不满
            isFull = false;
        }
        isFull=isFull&&(leftInfo.isFull)&& rightInfo.isFull;
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        return new Info(height, isFull);
    }


    public static boolean isFull2(Node head) {
        if (head == null) {
            return true;
        }
        Info1 all = process1(head);
        return (1 << all.height) - 1 == all.nodes;
    }

    public static class Info1 {
        public int height;
        public int nodes;

        public Info1(int h, int n) {
            height = h;
            nodes = n;
        }
    }

    public static Info1 process1(Node head) {
        if (head == null) {
            return new Info1(0, 0);
        }
        Info1 leftInfo = process1(head.left);
        Info1 rightInfo = process1(head.right);
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        int nodes = leftInfo.nodes + rightInfo.nodes + 1;
        return new Info1(height, nodes);
    }

    public static void main(String[] args) {
        int maxLevel = 5;
        int maxValue = 100;
        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++) {
            Node head = generateRandomBST(maxLevel, maxValue);
            if (isFull(head) != isFull2(head)) {
                System.out.println("Oops!");
                isFull(head);
            }
        }
        System.out.println("finish!");
    }
}
